Historically, computers, including computing systems and computing devices, were single-threaded. This means that at any given time, only one computer program, or task or thread of a computer program, was being executed. If a given thread was accessing a particular data value, the thread did not have to be concerned that other threads, or other tasks, were also accessing the data value. Therefore, the thread could read and update the data value as desired.
More recently, multi-threaded computers have become popular. Multi-threaded computers include single-processor systems that provide for multitasking, which allow for more than one thread or task of the same or different programs to be running at the same time, with the processor switching between executions of a number of different tasks over time. Multi-threaded computers also include multiple-processor systems, in which multiple threads and tasks of the same or different computer programs are concurrently running.
A reader of a data value is a thread or a task of a computer program, or other computer program code that is reading the data value. An updater of a data value is representative of a thread or a task of a computer program that is updating the data value. In multi-threaded systems, however, a given thread or task of a computer program cannot be guaranteed that it is the only reader or updater of a particular data value or data values.
For example, there may be a first data value and a second data value, where the second data value is dependent on the first data value, such that the first data value must first be updated and then the second data value must be updated. Furthermore, it must be guaranteed that readers first see the updated first data value before they see the updated second value. A concrete example of such data values is the providing of permissions to files within a file system. For a given file or group of files, there may be both an access control list (ACL) that governs access, as well as a set of permission bits that governs access. The ACL is a relatively granular access control, in that specific users, or groups of users, can be specified. By comparison, permission bits are less granular, in that either the owner of files can be specified, or a group of users including the owner of the files can be specified, and not just specific users within the group.
Consider the situation where the ACL and the permission bits for one or more files enable just the owner of the files, Frank, to access them. Frank is a member of a group that also includes Bob and Alice. The ACL may specify that the entire group, including Alice, Bob, and Frank, has access to the files. However, if the permission bits just specify Frank, then only Frank can access the files. This is because the access control mechanisms are restrictive in a conjunctive manner—both the ACL and the permission bits must provide a given user with access in order for that user to have access to the files. In this example, only Frank is given access by both the ACL and the permission bits, so only Frank has access to the files.
Now, Frank may want Bob to have access to the files, too, but not Alice. This requires two changes. First, the ACL must be updated to specify Bob and Frank, but not Alice. Second, the permission bits must be updated so that the group of users including Bob has access to the files. The permission bits allow Alice, Bob, and Frank to have access to the files, but because the ACL only specifies Bob and Frank, Alice does not obtain access to them.
For this modification in access to the files to work, the ACL has to be updated before the permission bits are updated. This is because if the permission bits are updated first, they will be updated to allow the entire group of users, Alice, Bob, and Frank, to have access to the files. Because the ACL originally specifies that the entire group of users has access, this means that if the permission bits are updated first, there will be a short period of time in which Alice has access, before the ACL is changed to restrict access to only Bob and Frank. The permission bits ultimately have to be updated to accord Bob access, because they originally specify that only Frank has access.
Furthermore, it has to be guaranteed that even if the ACL is updated before the permission bits are updated, any readers of the ACL and the permission bits see the updated ACL before the updated permission bits. As before, if a reader sees the updated permission bits before the updated ACL, it may improperly give Alice access to the files, which is not desired. Readers, therefore, have to see the changes made to the ACL before they see the changes made to the permission bits.
One way to ensure that the ACL is updated before the permission bits are and that readers see the updated ACL before the updated permission bits is to employ locks. An updater may, for instance, place locks on both the ACL and the permission bits. The updater updates the ACL first, then updates the permission bits, and finally releases the locks on both the ACL and the permission bits. While the updater has locks on the ACL and the permission bits, no other updater, and no reader, can access the ACL and the permission bits. However, locks can inflict an unacceptable degradation in performance, and therefore can be undesirable in some situations.
Another way to ensure that the ACL is updated before the permission bits are and that readers see the updated ACL before the updated permission bits is to force updaters to wait for a length of time after making any update. Thus, an updater may update the ACL, be forced to wait for a length of time, then update the permission bits, and be forced to wait for another length of time. The length of time is sufficiently long that any readers of both the ACL and the permission bits will always see the updated ACL before they see the updated permission bits.
However, forcing updaters to wait for a length of time after making any update introduces needless latency in many situations. For example, the system has no way of knowing that an update to the ACL will be followed by an update to the permission bits. Where the ACL is updated, but not the permission bits, the updater still has to wait for the length of time after updating the ACL. Similarly, where the updater is just updating the permission bits, it still has to wait for the length of time after making the update. Such excessive and unneeded latency may cause system-wide performance degradation.
An additional way to ensure that the ACL is updated before the permission bits are and that readers see the updated ACL before the updated permission bits is to use barriers of the type employed in high-performance computing (HPC) systems, to separate an update to the ACL from an update to the permission bits. Thus, the update to the ACL is made, a barrier is imposed, an update to the permission bits is made, and then the barrier is removed. The barrier prevents readers from seeing the updated permission bits before seeing the updated ACL. However, such barriers involve high overhead typically, similar to as in employing locks. Furthermore, such barriers impose “data skew,” in the sense that threads that arrive at the barrier must wait idly, wasting time that could otherwise be used.
For these and other reasons, therefore, there is a need for the present invention: